package leet77combination

// 思路：
// 使用回溯算法生成从1到n的所有长度为k的组合。
// 回溯算法的核心是递归地构建组合，并在每次递归时检查当前组合的长度是否达到k。
// 当组合长度达到k时，将其添加到结果列表中。
// 该函数从1开始递归地添加数字到当前组合中，直到组合长度达到k。
// 最终返回所有生成的组合。
func Combine(n int, k int) [][]int {
	result := [][]int{}

	if k > n || k <= 0 {
		return result
	}
	// path用于存储当前的组合
	path := []int{}
	// 回溯函数，start参数用于控制从哪个数字开始添加到组合中
	var backtrack func(start int)
	backtrack = func(start int) {
		// 如果当前组合的长度等于k，将其添加到结果中
		// 否则继续添加下一个数字
		if len(path) == k {
			temp := make([]int, k)
			copy(temp, path)
			result = append(result, temp)
			return
		}
		// 从start开始遍历到n，尝试添加每个数字到当前组合中
		// 这里的start确保了组合中的数字是递增的，避免重复组合
		for i := start; i <= n; i++ {
			path = append(path, i)
			backtrack(i + 1)
			// 回溯，移除最后添加的数字，尝试下一个数字
			path = path[:len(path)-1]
		}
	}
	backtrack(1)
	return result
}

// Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient.
// Space Complexity: O(k), for the path used in backtracking.
// C(n, k) is the number of combinations of n items taken k at a time.
// The time complexity is dominated by the number of combinations generated, which is C(n, k).
// The space complexity is O(k) due to the path used in the backtracking process.
// The function generates all combinations of k numbers from the range 1 to n.
// It uses backtracking to explore all possible combinations, ensuring that each combination is of length k.
// The function starts from 1 and goes up to n, recursively building combinations by adding the current number to the path.
// When the path reaches the desired length k, it is added to the result list.
// The function handles edge cases where k is greater than n or k is less than or equal to 0 by returning an empty result.
// The function is efficient for generating combinations and can handle moderate values of n and k.
// The function is designed to be used in scenarios where combinations of a specific length are needed, such as in combinatorial problems or generating subsets.
